#define _CRT_SECURE_NO_WARNINGS 1
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> mp;
    Node* dfs(Node* node) {
        if (mp[node])return mp[node];
        Node* newnode = new Node(node->val);
        mp[node] = newnode;
        for (int i = 0; i < node->neighbors.size(); i++) {
            newnode->neighbors.push_back(dfs(node->neighbors[i]));
        }
        return newnode;
    }
    Node* cloneGraph(Node* node) {

        if (node == nullptr)return nullptr;

        return dfs(node);
    }
};